/*
 * @Author: szx
 * @Date: 2021-11-17 13:14:44
 * @LastEditTime: 2021-12-29 13:40:48
 * @Description:
 * @FilePath: \leetcode\1-99\47\47.js
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    nums.sort((a, b) => a - b);
    let res = [],
        path = [],
        used = [];

    const dfs = () => {
        if (path.length == nums.length) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            // 填过了，或者是使用过了，这里注意used[i-1]==false是使用过了因为被复原回了false了，属于同一层的使用
            // used[i-1]==true是正在使用，属于递归上的树枝
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            // 没填过，填一下
            path.push(nums[i]);
            used[i] = true;
            dfs();
            // 填完了记得变回去
            path.pop();
            used[i] = false;
        }
    };
    dfs();
    return res;
};

var permuteUnique = function (nums) {
    nums.sort((a, b) => a - b);
    const len = nums.length;
    const res = [];
    const path = [];
    const used = new Array(len).fill(false);
    const backtrace = () => {
        if (path.length == len) {
            res.push(path.slice());
            return;
        }
        for (let i = 0; i < len; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            path.push(nums[i]);
            used[i] = true;
            backtrace();
            used[i] = false;
            path.pop();
        }
    };
    backtrace();
    return res;
};
console.log(permuteUnique([1, 2, 3, 3, 3]));
